package structure.tree;


import java.util.LinkedList;
import java.util.Stack;

public class MyBinaryTree {


    // 最大深度 -
    public Integer maxDepth(TreeNode node){
        if (node == null){
            return 0 ;
        }
        Integer left = maxDepth(node.left);
        Integer right = maxDepth(node.right);
        return Math.max(left,right) + 1;
    }

    // 最小深度
    public Integer minDepth(TreeNode node){
        if (node == null){
            return 0;
        }

        if (node.left == null || node.right == null){
            return 1;
        }
        Integer left = minDepth(node.left);
        Integer right = minDepth(node.right);
        return Math.min(left,right) + 1;
    }

    // 全部节点个数
    public Integer allNodeNum(TreeNode treeNode){

        if (treeNode == null){
            return 0;
        }
        Integer left = allNodeNum(treeNode.left);

        Integer right = allNodeNum(treeNode.right);
        return left + right + 1;
    }

    // 全部叶子节点个数
    public Integer allSubNodeNum(TreeNode treeNode){

        if (treeNode == null){
            return 0;
        }
        if (treeNode.left == null && treeNode.right == null){
            return 1;
        }
        return allSubNodeNum(treeNode.left) + allSubNodeNum(treeNode.right);
    }


    public TreeNode findByValue(TreeNode node, Integer value) {
        if (node == null){
            return null;
        }
        while (true){
            if (node.value == value){
                return node;
            }if (node.value > value){
                node = node.left;
            }else {
                node = node.right;
            }
            if (node == null){
                return null;
            }
        }

    }

    // 广度遍历 - 层序遍历
    public void LevelOrder(TreeNode node) {
        if (node == null){
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList();
        queue.offer(node);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.println(cur.value);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    // 深度遍历
    public void depthOrder(TreeNode node){
        if (node == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            System.out.println(cur.value);
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left != null){
                stack.push(cur.left);
            }
        }

    }


    // 前序遍历
    public void preOder(TreeNode node){
        if (node == null){
            return;
        }
        System.out.println(node.value);
        preOder(node.left);
        preOder(node.right);
    }

    // 中遍历
    public void midOder(TreeNode node){
        if (node == null){
            return;
        }
        preOder(node.left);
        System.out.println(node.value);
        preOder(node.right);
    }

    // 后续遍历
    public void lastOder(TreeNode node){
        if (node == null){
            return;
        }
        preOder(node.left);
        preOder(node.right);
        System.out.println(node.value);
    }




    //    5
    //  1   8
    // 0 2 6 9
    class TreeNode{
        private Integer value;
        private TreeNode left;
        private TreeNode right;

        TreeNode(Integer value){
            this.value = value;
        }
    }
}
